/*
 * @lc app=leetcode.cn id=924 lang=cpp
 *
 * [924] 尽量减少恶意软件的传播
 */
#include "include.h"
// @lc code=start
class Solution {
public:
    int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
        nodeNum_ = graph.size();
        visited_.resize(nodeNum_, 0);

        int minInfectedNodeNum = nodeNum_;
        int minInfectedNodeIndex = 0;
        for (int i=0;i<nodeNum_;i++){
            int finalInNum = finalInfectedNum(graph, initial, i);
            if (finalInNum < minInfectedNodeNum){
                minInfectedNodeNum = finalInNum;
                minInfectedNodeIndex = i;
            }
        }

        return minInfectedNodeIndex;
    }
private:
    int finalInfectedNum(vector<vector<int>>& graph, 
                         vector<int>& initial, 
                         int removeIndex){
        infectedNodeCounter_ = 0;
        memset(visited_.data(), 0, nodeNum_*sizeof(int));
        for (int i=0;i<nodeNum_;i++){
            if (visited_[i] == 1 or i == removeIndex){continue;}
            dfs(graph, i);
        }
        return infectedNodeCounter_;
    }
    int infectedNodeCounter_;
    int nodeNum_;
    vector<int> visited_;
    void dfs(vector<vector<int>>& graph, int nodeIndex){
        infectedNodeCounter_ += 1;
        visited_[nodeIndex] = 1;
        for (int j=0;j<nodeNum_ and j!=nodeIndex;j++){
            if (graph[nodeIndex][j] == 1
                and visited_[j] == 0){
                dfs(graph, j);
            }
        }
    }
};
// @lc code=end

